1. Field of the Invention
The present invention relates to a method for dynamically using a compiler in executing a bytecode which is an intermediate code of Java(trademark) (a trademark of Sun Microsystems, Inc.), Smalltalk, and the like.
2. Background of the Invention
Conventionally, in a bytecode interpreter of a virtual machine in Java(trademark), Smalltalk, and the like, optimization is often performed by compiling (at execution time) those bytecodes which are frequently executed. This optimization is achieved by determining the frequency that each method is called and comparing the results to a threshold value. Only those methods with call frequencies that exceed the threshold are compiled, saving overall compilation time.
However, in the above-mentioned conventional method, frequency of calling a method is a trigger for compilation; therefore, even if a loop whose iteration number is huge is included in a method, it is not selected for compilation
An object of the present invention is to solve the above-mentioned problem and detect a method including a loop and estimate an effect of compiling the method at a low cost at an execution time so as to provide a method for a more efficient bytecode execution by selecting an execution mode according to the estimation.
Another object of the present invention is to provide a method for enabling more efficient processing of an interpreter and a compiler by recording an execution history of a conditional branch instruction and the like simultaneously with detection of a loop.
In the method for determining a dynamic compilation time which is the first form of the present invention, first, at a time of a bytecode execution by an interpreter, if an instruction to be executed is a backward conditional branch instruction, it is determined whether the backward conditional branch instruction is a back edge of a loop. And if it is determined the instruction is a back edge of a loop, the number of the loop iteration is estimated and stored into a storage. The time of compilation is determined according to the estimated number of the loop iteration.
In the method for selecting a bytecode execution mode which is the second form of the present invention, first, at a time of a bytecode execution by an interpreter, if an instruction to be executed is a backward conditional branch instruction, it is determined whether the backward conditional branch instruction is a back edge of a loop. And if it is determined the instruction is a back edge of a loop, the number of the loop iteration is estimated and stored into a storage. A bytecode execution mode is selected according to the estimated number of the loop iteration.
In a suitable form of embodiment, an execution mode comprises the modes of immediately compiling a method including a loop; and having the interpreter execute a bytecode. In a further suitable form of embodiment, the mode of immediately compiling a method including a loop comprises a predetermined number of modes whose optimization levels were changed according to the estimated number of the loop iteration. It is also possible, in the mode of having the interpreter execute a bytecode, to organize it so that the time of compiling a method including a loop is determined according to the estimated number of the loop iteration.
Determination in the first and second forms of the present invention, of whether the backward conditional branch instruction is a back edge of a loop, is suitably performed by pattern matching using state transition of a bytecode sequence comprised of a predetermined number of instructions prior to the conditional branch instruction and a bytecode sequence corresponding to an actual back edge of a loop. In addition, suitably, the number of the loop iteration is estimated from operands of a predetermined number of instructions prior to the conditional branch instruction. More suitably, an operation code of the conditional branch instruction which determined whether the instruction is a back edge of a loop is modified to indicate that it is already determined and/or whether a conditional branch has been taken.
While a flow of processing of the present invention is explained as above, the present invention can also be implemented by a device for implementing these processes or in a form of a program for having a computer implement these processes. Storing of this program on storage media such as a floppy disk, CD-ROM, or any other form of storage is well understood by one having ordinary skill in the art.